import java.util.Random;

class Solution {

    private static final Random R = new Random();

    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    private void heapSort(int[] nums) {
        int n = nums.length;

        for (int i = n / 2; i >= 0; i--) {
            heapify(nums, i, n - 1);
        }

        int last = n - 1;
        int index = 0;

        for (int i = 0; i < n; i++) {
            swap(nums, 0, last);
            last--;
            heapify(nums, 0, last);
        }
    }

    private void heapify(int[] nums, int curr, int boundary) {
        int left = curr * 2 + 1, right = curr * 2 + 2;
        int index = curr;

        if (left <= boundary && nums[left] > nums[index]) {
            index = left;
        }

        if (right <= boundary && nums[right] > nums[index]) {
            index = right;
        }

        if (index != curr) {
            swap(nums, curr, index);
            heapify(nums, index, boundary);
        }
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = partition1(nums, start, end);

        quickSort(nums, start, mid - 1);
        quickSort(nums, mid + 1, end);
    }

    private int partition1(int[] nums, int start, int end) {
        int r = R.nextInt(end - start + 1) + start;
        int pivot = nums[r];
        swap(nums, start, r);
        int left = start, right = end;

        while (left < right) {
            while (left < right && nums[right] > pivot) {
                right--;
            }

            while (left < right && nums[left] <= pivot) {
                left++;
            }

            if (left < right) {
                swap(nums, left, right);
            }
        }

        swap(nums, start, right);

        return right;
    }

    private int partition2(int[] nums, int start, int end) {
        int r = R.nextInt(end - start + 1) + start;
        int pivot = nums[r];
        swap(nums, start, r);
        int left = start + 1, right = end;

        while (left <= right) {
            while (left <= right && nums[right] >= pivot) {
                right--;
            }

            while (left <= right && nums[left] < pivot) {
                left++;
            }

            if (left < right) {
                swap(nums, left, right);
            }
        }

        swap(nums, start, right);

        return right;
    }

    private int partition3(int[] nums, int start, int end) {
        int r = R.nextInt(end - start + 1) + start;
        int pivot = nums[r];
        swap(nums, start, r);
        int slow = start + 1, fast = slow;

        while (fast <= end) {
            if (nums[fast] <= pivot) {
                swap(nums, slow, fast);
                slow++;
            }

            fast++;
        }

        swap(nums, start, --slow);

        return slow;
    }



    private void swap(int[] nums, int a, int b) {
        if (a == b) return;

        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}